package com.aurora.leetcode.answer.dynamic_plan;

/**
 * @author : qiaodan
 * @date : 2025/4/24 20:42
 * @description 给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返
 * 回其最大和。
 * 子数组 是数组中的一个连续部分。
 * 示例1：
 * 输入：nums - [-2,1,-3,4,-1,2,1,-5,4]
 * 输出：6
 * 解释：连续子数组  [4,-1,2,1〕 的和最大，为6
 * 示例 2：
 * 输入： nums =[1]
 * 输出：
 * 示例3：
 * 输入：numg
 * [5, 4, -1, 7, 8]
 * 输出：23
 * 提示：
 * 1 ＜= nums.Length <= 105
 * -104 <= nums[i] <= 104
 * 进阶：如果你已经实现复杂度为 o(n）的解法，尝试使用更为精妙的 分治法 求解。
 */
public class MaxSubArray_53 {

    /**
     * 我的实现：二维数组 超出空间限制
     *
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int length = nums.length;
        int[][] mark = new int[length + 1][length + 1];
        int maxValue = Integer.MIN_VALUE;
        for (int i = 0; i < length; ++i) {
            mark[i + 1][i + 1] = nums[i];
            if (nums[i] > maxValue) {
                maxValue = nums[i];
            }
        }
        for (int i = 1; i <= length; ++i) {
            for (int j = 1; j <= length; ++j) {
                if (i != j) {
                    mark[i][j] = mark[i][j - 1] + mark[j][j];
                    if (mark[i][j] > maxValue) {
                        maxValue = mark[i][j];
                    }
                }
            }
        }
        return maxValue;
    }

    /**
     * 参考实现：动态规划
     * 实现思路：要么从前面的位置累加过来，要么重新开始
     * dp[i] = max(dp[i-1] + nums[i]， nums[i])
     * 其中，dp[i]表示以第i个元素结尾的最大连续子数组和
     *
     * @param nums
     * @return
     */
    public int maxSubArray2(int[] nums) {
        int curNum = nums[0];
        int maxValue = curNum;
        for (int i = 1; i < nums.length; ++i) {
            curNum = Math.max(curNum + nums[i], nums[i]);
            if (curNum > maxValue) {
                maxValue = curNum;
            }
        }
        return maxValue;
    }


    /**
     * 参考实现：分治法
     * 思路：将数组分成两部分，分别求
     * 左边最大子数组的和
     * 右边最大子数组的和
     * 跨越中间点的最大子数组的和
     *
     * @param nums
     * @return
     */
    public int maxSubArray3(int[] nums) {
        return splitArray(nums, 0, nums.length - 1);
    }

    public int splitArray(int[] nums, int left, int right) {
        if (left >= right)
            return nums[left];
        int mid = (left + right) / 2;
        int leftNum = splitArray(nums, left, mid);
        int rightNum = splitArray(nums, mid + 1, right);
        int midNum = calculateCrossArray(nums, left, mid, right);
        return Math.max(midNum, Math.max(leftNum, rightNum));
    }

    public int calculateCrossArray(int[] nums, int left, int mid, int right) {
        int leftNum = Integer.MIN_VALUE;
        int curLeftNum = 0;
        for (int i = mid; i >= left; --i) {
            curLeftNum += nums[i];
            if (curLeftNum > leftNum) {
                leftNum = curLeftNum;
            }
        }

        int rightNum = Integer.MIN_VALUE;
        int curRightNum = 0;
        for (int i = mid+1; i <= right; ++i) {
            curRightNum += nums[i];
            if (curRightNum > rightNum) {
                rightNum = curRightNum;
            }
        }

        return leftNum + rightNum;

    }


    public static void main(String[] args) {
//        int[]nums = new int[]{-2,1,-3,4,-1,2,1,-5,4}; //6
//        int[]nums = new int[]{1}; //1
//        int[] nums = new int[]{5, 4, -1, 7, 8}; //23
        int[] nums = new int[]{-2,-1};// -1
        MaxSubArray_53 maxSubArray53 = new MaxSubArray_53();
//        System.out.println(maxSubArray53.maxSubArray(nums));
//        System.out.println(maxSubArray53.maxSubArray2(nums));
        System.out.println(maxSubArray53.maxSubArray3(nums));
    }
}
